ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group93c.txt/000106_icon-group-sender _Wed Dec 1 10:01:23 1993.msg

Internet Message Format | 1994-02-02 | 27KB

Received: by cheltenham.cs.arizona.edu; Wed, 1 Dec 1993 10:02:19 MST
Date: Wed, 1 Dec 93 10:01:23 MST
From: gmt (Gregg Townsend)
Message-Id: <[e-mail]>
To: icon-group
Subject: set insertion during generation
Content-Length: 25796
Status: R
Errors-To: [e-mail]

[ Here are several related messages from the comp.lang.icon newsgroup,
  forwarded to the Icon-group mailing list as one long message. ]

------------------------------------------------------------------------

From: [e-mail] (Norman Ramsey)
Organization: Bellcore
Date: Tue, 23 Nov 1993 03:50:18 GMT

What guarantees does Icon provide if I alter a structured value in the
middle of generating elements of that value?
  s := set()
   ...
  every x := !s do if p(x) then delete(s, x) else insert(s, [x])

Is open(mumble, "bp") legitimate, and if so, what are its semantics?
(I want to write, e.g.,  `nntpserver := open("telnet foo 119", "bp")'
and have my Icon program talk to an NNTP server.)

Norman
--
Norman Ramsey
[e-mail]

------------------------------------------------------------------------

From: [e-mail] (Nevin Liber)
Date: 23 Nov 1993 05:59:38 -0700
Organization: University of Arizona CS Department, Tucson AZ

In article <[e-mail]>,
Norman Ramsey <[e-mail]> wrote:

>What guarantees does Icon provide if I alter a structured value in the
>middle of generating elements of that value?
>  s := set()
>   ...
>  every x := !s do if p(x) then delete(s, x) else insert(s, [x])

None, I believe.  What kind if guarantees were you expecting?  You are
generating elements from a collection of unordered (important point
here), unique elments.  Any guarantees that I can think of would force
order on that collection.

In reality, if you use ! on the same set twice, you get the elements in
the same order, because from an implementation point of view, it takes
work to create a nonpredictable, random order for things.  But
implementations can change.

If you want a guarantee like, say, all elements of the original set
should be generated, you could use a construct like:

every x := !copy(s) do ...

>Is open(mumble, "bp") legitimate, and if so, what are its semantics?

I believe that it is legitimate.  Although its been a while since I
looked the Icon source code, I believe that it just passes the flags
down to C, so it would have the same semantics as opening a pipe under
C.
--
    Nevin ":-)" Liber    [e-mail]    [phone]

------------------------------------------------------------------------

From: Darren New <[e-mail]>
Organization: Bellcore
Date: Tue, 23 Nov 1993 14:16:25 GMT

> >What guarantees does Icon provide if I alter a structured value in the
> >middle of generating elements of that value?
> None, I believe.  What kind if guarantees were you expecting?
Perhaps the kind of guarantee that the Hermes language offers, which is
that the effect of the iterator is as if the tabler/set/list/whatever
being iterated over is copied before iteration starts (which is, I
think, what the compiler does if there are any modifications to its
contents within the scope of the loop). Nothing to do with the order of
iteration at all.

That is, I think the point is "if I insert an element into a set I'm
iterating over, will it always/never/sometimes show up in the
iteration?"

> In reality, if you use ! on the same set twice, you get the elements in
> the same order, because from an implementation point of view, it takes
> work to create a nonpredictable, random order for things.  But
> implementations can change.
Actually, there was talk of assuring different orders of iteration
during different runs of a Hermes program, merely to prevent programs
from being accidentally written that depend on the order of iteration.
Now *that* is user-friendly.  :-)

------------------------------------------------------------------------

From: [e-mail] (Steve Wampler)
Organization: National Optical Astronomy Observatories, Tucson AZ
Date: Tue, 23 Nov 1993 15:24:30 GMT

In article <[e-mail]>, Darren New <[e-mail]> writes:
|> > >What guarantees does Icon provide if I alter a structured value in the
|> > >middle of generating elements of that value?
|> > None, I believe.  What kind if guarantees were you expecting?
|> Perhaps the kind of guarantee that the Hermes language offers, which is
|> that the effect of the iterator is as if the tabler/set/list/whatever
|> being iterated over is copied before iteration starts (which is, I
|> think, what the compiler does if there are any modifications to its
|> contents within the scope of the loop). Nothing to do with the order of
|> iteration at all.

Careful.  Icon doesn't iterate over objects, but across result sequences.
(I.e. every just drives goal-directed evaluation(GDE) through all
results of an expression.)  I don't think you'd want to use a language
that copied all data objects in expressions that are involved in GDE!

consider:

every a <- !s1 || !s2 || !s3 do {...}

how many copies of s3 would have to be produced during evaluation of this?
(And I would imagine the evaluation mechanism would have to be pretty
complicated to manage the above...)

Finally, what about the cases where you're not driving GDE with an every,
but there is still GDE taking place?  e.g.:

match(!s1 || !s2, !s3)

again, I think there'd be a pretty hefty performance hit to provide
any sort of 'guarantee'.  (Not to mention the complexity if !s3 is
replaced with f(s3).)

------------------------------------------------------------------------

From: [e-mail] (Darren New)
Date: 23 Nov 93 17:02:00 GMT
Organization: Bellcore

> Careful.  Icon doesn't iterate over objects, but across result sequences.

This is a good point. But Hermes iterates over "tables"  (i.e.,
relational database-like tables) so that doesn't come up here. It also
only copies when such copying is needed to ensure the semantics.

> (I.e. every just drives goal-directed evaluation(GDE) through all
results of an expression.)

This kind of begs the question, tho. What's the behavior of ! in this
case, then? If "every" is just the GDE control structure, then "!"
should have some defined semantics (or explicitly undefined semantics,
yuck) as to what it does if the argument is changed while suspended.

I wasn't arguing for copying, BTW. That was just an example of
semantics. Another example might be to give a function body (including
suspends, returns, and fails) that is the equivalent of each built in
operator (like !). Something like the listing of "tab()" on page 178 of
the second ed of The Icon Programming Language.

> again, I think there'd be a pretty hefty performance hit to provide
> any sort of 'guarantee'.  (Not to mention the complexity if !s3 is
> replaced with f(s3).)

Well, I would rather have a performance hit than have a program that
works fine with one version of Icon and coredumps with another. That
sounds too much like C to me.  ;-)
If I need to copy it in some circumstances (e.g., I'm adding a new
element to a set for every element already in the set) then I need to
know whether I'm going to see all the new elements or not. If I *might*
see the new elements, that's a guarantee too, in that I'm guaranteed to
have to copy the set myself before starting. But leaving it undefined
tends to cause people to "try and see," which works poorly when you
upgrade the interpreter, or use the compiler instead, or port it from
UNIX to MS-DOS, or whatever.       -- Darren

------------------------------------------------------------------------

From: [e-mail] (Marc Espie)
Organization: LIENS, ENS, 45 rue d'Ulm, Paris (France)
Date: Wed, 24 Nov 93 09:45:13 GMT

In article <[e-mail]> [e-mail] (Darren New) writes:
[...]
>
>I wasn't arguing for copying, BTW. That was just an example of
>semantics. Another example might be to give a function body (including
>suspends, returns, and fails) that is the equivalent of each built in
>operator (like !). Something like the listing of "tab()" on page 178 of
>the second ed of The Icon Programming Language.
>
>> again, I think there'd be a pretty hefty performance hit to provide
>> any sort of 'guarantee'.  (Not to mention the complexity if !s3 is
>> replaced with f(s3).)
>
>Well, I would rather have a performance hit than have a program that
>works fine with one version of Icon and coredumps with another. That
>sounds too much like C to me.  ;-)
>If I need to copy it in some circumstances (e.g., I'm adding a new
>element to a set for every element already in the set) then I need to
>know whether I'm going to see all the new elements or not. If I *might*
>see the new elements, that's a guarantee too, in that I'm guaranteed to
>have to copy the set myself before starting. But leaving it undefined
>tends to cause people to "try and see," which works poorly when you
>upgrade the interpreter, or use the compiler instead, or port it from
>UNIX to MS-DOS, or whatever.       -- Darren
>
Ok, how about that for a semantics: if you try and add an element to the
set while you're scanning it and resume the scan, you get a runtime error.

Sounds pretty reasonable to me.
- cheap to implement.
- well-defined semantics.

What are you doing adding elements to a set while you're scanning it anyway ?
That's unelegant, relies on side-effects, and not a good idea anyway.
One very good thing about Icon is: keep it simple. Understandable semantics,
orthogonal language, everything set up carefully...

Anyway, considering the overall structure of the language, except IF you're
a very, very naughty programmer, such a hack as adding an element in the
middle of a scan would be fixed in a jiffy.


--
[nosave]
     Marc Espie ([e-mail])
``I'm gonna dance the dream
And make the dream come true''

------------------------------------------------------------------------

From: [e-mail] (Darren New)
Date: 24 Nov 93 14:16:36 GMT
Organization: Bellcore

> Ok, how about that for a semantics: if you try and add an element to the
> set while you're scanning it and resume the scan, you get a runtime error.
Sounds reasonable to me.  Better than having it work on some platforms
and fail on others.

> What are you doing adding elements to a set while you're scanning it anyway ?
> That's unelegant, relies on side-effects, and not a good idea anyway.
Oh baloney. Take a set of employee's names. Iterate thru it and add to
it the set of spouses of those names. You now have the set of people
covered by the insurance.  There's lots of reasons why you'd want to do
something like that.  I don't see why it's more elegant to use two sets
(if the semantics said you needn't, which they don't in Icon), and I
don't see why relying on side-effects is a problem in a language like
Icon.

> Understandable semantics,
Debatable, as this discussion shows...
> orthogonal language, everything set up carefully...
Yes. Icon *is* very nice. No question there.  Most of my code works the
first time it runs to completion without a run-time error. And most of
the run-time errors are pretty trivial to fix, on the order of syntax
errors.

> such a hack as adding an element in the middle of a scan would be fixed
> in a jiffy.
Sure, if the semantics were "don't do this."
It's a shame there aren't more languages with formal semantics of some form.


--
445 South St/MRE 2E-279/Morristown NJ 07960 USA/[phone]
Delivery of Electronic Multimedia over Networks (DEMON)
Also, formal description techniques, programming languages.
``Your fault: Core dumped.''                EFF#846
``Sometimes, you just have to bite the silver bullet.''

------------------------------------------------------------------------

From: [e-mail] (Nevin Liber)
Date: 24 Nov 1993 12:22:39 -0700
Organization: University of Arizona CS Department, Tucson AZ

In article <[e-mail]>,
Darren New  <[e-mail]> wrote:
>Perhaps the kind of guarantee that the Hermes language offers, which is
>that the effect of the iterator is as if the tabler/set/list/whatever
>being iterated over is copied before iteration starts (which is, I
>think, what the compiler does if there are any modifications to its
>contents within the scope of the loop).

If you need that guarantee, it is fairly easy to implement (generate
over copy(s) instead of s).

Personally, just about all my code doesn't modify a data structure if
it is being generated upon via !.

>That is, I think the point is "if I insert an element into a set I'm
>iterating over, will it always/never/sometimes show up in the
>iteration?"

Sometimes (it "generates" them in the order it is stored in the
internal hash table, I believe.)

>Actually, there was talk of assuring different orders of iteration
>during different runs of a Hermes program, merely to prevent programs
>from being accidentally written that depend on the order of iteration.
>Now *that* is user-friendly.  :-)

For development, I totally agree.  However, once I am done
writing/debugging/modifying the code, I don't want to pay this
performance penalty.  I'd rather have the computer spending its cycles
doing useful work for me.
--
    Nevin ":-)" Liber    [e-mail]    [phone]

------------------------------------------------------------------------

From: [e-mail] (Nevin Liber)
Date: 24 Nov 1993 12:40:13 -0700
Organization: University of Arizona CS Department, Tucson AZ

In article <[e-mail]>,
Darren New <[e-mail]> wrote:

>case, then? If "every" is just the GDE control structure, then "!"
>should have some defined semantics (or explicitly undefined semantics,
>yuck) as to what it does if the argument is changed while suspended.

I disagree with the "yuck" part of your statement.  Typically, if you
are pressed to define the semantics for something uncommon (like
modifying a structure you are iterating over), you pretty much lock
yourself into only one possible implementation.  Also, from a code
maintenance point of view, this makes the language harder to master
because there are more of these special cases to memorize.

Here is an example:  in the map(sString, sSource, sDestination) function,
is disambiguation of duplicate characters in sSource done left-to-right
or right-to-left?  Wouldn't it have been simpler to just say this
results in undefined behavior and should be avoided, than to pin it down
based on the implementation?  As a matter of fact, if there was a
"debug" version of Icon, it could actually check for these violations,
while in the "production" version, you don't get the performance hit.

>Well, I would rather have a performance hit than have a program that
>works fine with one version of Icon and coredumps with another.

While I'm developing something, I totally agree with you.  But I don't
want my production system to suffer because of these checks.

>If I need to copy it in some circumstances (e.g., I'm adding a new
>element to a set for every element already in the set) then I need to
>know whether I'm going to see all the new elements or not.

I don't see how you can ask for this, without wanting an implicit order
on the set (eg: by time) or copy first semantics (which is still
ordering by time; it just says that you don't want any elements
produced after the set was instanciated by !).

>If I *might*
>see the new elements, that's a guarantee too, in that I'm guaranteed to
>have to copy the set myself before starting.

That's all I would count on.  It's the "safest" assumption.  Anything
else would make me look it up every time I saw it.

>But leaving it undefined
>tends to cause people to "try and see," which works poorly when you
>upgrade the interpreter, or use the compiler instead, or port it from
>UNIX to MS-DOS, or whatever.

Agreed.  Actually, a good reference on this kind of stuff is "Writing
Solid Code", by Steve MaGuire, published by Microsoft Press.
--
    Nevin ":-)" Liber    [e-mail]    [phone]

------------------------------------------------------------------------

From: [e-mail] (Nevin Liber)
Date: 24 Nov 1993 12:49:04 -0700
Organization: University of Arizona CS Department, Tucson AZ

In article <[e-mail]>,
Marc Espie <[e-mail]> wrote:

>Ok, how about that for a semantics: if you try and add an element to the
>set while you're scanning it and resume the scan, you get a runtime error.

>Sounds pretty reasonable to me.
>- cheap to implement.
>- well-defined semantics.

I'm not convinced that it is all that cheap to implement (then again,
I'm really sleepy right now, so take what I say with a grain of salt
:-)).  Consider the following code fragment:

every x := !S do {
    ...
    insert(S, foo)
    ...
    every y := !S do {
        ...
    }
}

How do you keep track of whether you are resuming the first one or the
second one (or the nth one, if being called recursively)?  I think that
this will get messy.

I also believe that run-time errors are a last-ditch bailing mechanism,
when you can't think of anything reasonable to do.  Then again, maybe
that does apply here.

>What are you doing adding elements to a set while you're scanning it anyway ?
>That's unelegant, relies on side-effects, and not a good idea anyway.

I agree with you 100% here, and never do it myself.
--
    Nevin ":-)" Liber    [e-mail]    [phone]

------------------------------------------------------------------------

From: [e-mail] (Nevin Liber)
Date: 24 Nov 1993 12:55:44 -0700
Organization: University of Arizona CS Department, Tucson AZ

In article <[e-mail]>,
Darren New <[e-mail]> wrote:
>> What are you doing adding elements to a set while you're scanning it anyway ?
>> That's unelegant, relies on side-effects, and not a good idea anyway.
>Oh baloney. Take a set of employee's names. Iterate thru it and add to
>it the set of spouses of those names. You now have the set of people
>covered by the insurance.  There's lots of reasons why you'd want to do
>something like that.  I don't see why it's more elegant to use two sets
>(if the semantics said you needn't, which they don't in Icon), and I
>don't see why relying on side-effects is a problem in a language like
>Icon.

Well, there is nothing wrong with doing that from a language point of
view.  However, I would claim that you are breaking the abstraction of
what that set stands for.  First it is a set of employee names; now it
is a set of people covered by insurance.  If I want to convert one of
these to another, I use two different variables, because I am naming
two different types of objects.  Unless you are really, really pressed
for space efficiency, I believe that it is much clearer to use two
different sets for this.
--
    Nevin ":-)" Liber    [e-mail]    [phone]

------------------------------------------------------------------------

From: [e-mail] (Norman Ramsey)
Organization: Bellcore
Date: Wed, 24 Nov 1993 21:06:44 GMT

>>What guarantees does Icon provide if I alter a structured value in the
>>middle of generating elements of that value?
>>  s := set()
>>   ...
>>  every x := !s do if p(x) then delete(s, x) else insert(s, [x])
>
>None, I believe.  What kind if guarantees were you expecting?

Here are some possible guarantees:
  - every element that was in s before `every' started executing will
    be generated
  - inserted elements might be generated, might not
  - inserted elements won't be generated
  - inserted elements will be generated
Here is what I fear:
  - the behavior of the construct is undefined

Norman

------------------------------------------------------------------------

From: [e-mail] (Norman Ramsey)
Organization: Bellcore
Date: Wed, 24 Nov 1993 21:10:31 GMT

>What are you doing adding elements to a set while you're scanning it anyway ?
>That's unelegant, relies on side-effects, and not a good idea anyway.

Nonsense.
  every x := !s & type(x) == "field" & insert(s, !extensions[x])
makes sure s is closed under the ``extensions'' relation.  (In this
case I needn't worry about generating elements of extensions[x]
because they never have type "field".)

------------------------------------------------------------------------

From: Darren New <[e-mail]>
Organization: Bellcore
Date: Wed, 24 Nov 1993 22:42:00 GMT

> First it is a set of employee names; now it
is a set of people covered by insurance.

Nope. I just want the people covered by insurance.  However, all I have
access to is two different tables: employees, and their spouses.  There
has to be an intermediate expression where only some of the people are
in the set. If nothing else, you can't generate a set of employees
because you have to insert them in the set one at a time, see. So at
*some* point the set will be "the set of employees I've gotten around to
inserting so far."  Maybe if we were using SQL I could do it with one
loop.  But that isn't always possible in Icon.

------------------------------------------------------------------------

From: [e-mail] (Gregg Townsend)
Date: 24 Nov 1993 17:37:51 -0700
Organization: University of Arizona CS Department, Tucson AZ

Fear not.  It is safe to insert and delete items of a set while the set is
being generated. Items that are neither inserted nor deleted are generated
exactly once.  Norman Ramsey and Darren New each gave an example of why
this is useful.

An inserted item may or may not be generated once, depending on enough
different factors that you might as well consider it random.

    Gregg Townsend / Icon Project / Computer Science Dept / Univ of Arizona
    [phone]     [e-mail]     110 57 16 W / 32 13 45 N / +758m

------------------------------------------------------------------------

From: [e-mail] (Nevin Liber)
Date: 28 Nov 1993 08:14:38 -0700
Organization: University of Arizona CS Department, Tucson AZ

In article <[e-mail]>,
Norman Ramsey <[e-mail]> wrote:
> Here are some possible guarantees:
> ...
>  - inserted elements might be generated, might not

>Here is what I fear:
>  - the behavior of the construct is undefined

I'm not sure why you accept the first statement as a useful guarantee,
and fear the second one.  From a practical point of view, I can find no
difference between statement one and statement two, as far as inserted
elements are concerned.  Is there any possible situation where you can
do something if statement one is guaranteed, vs it being undefined?
--
    Nevin ":-)" Liber    [e-mail]    [phone]

------------------------------------------------------------------------

From: [e-mail] (Norman Ramsey)
Date: 29 Nov 93 02:02:11 GMT
Organization: Bellcore, Morristown NJ

In article <2daf8u$[e-mail]>,
Nevin Liber <[e-mail]> wrote:
>>  - inserted elements might be generated, might not
>>  - the behavior of the construct is undefined
>
>I'm not sure why you accept the first statement as a useful guarantee,
>and fear the second one.  From a practical point of view, I can find no
>difference between statement one and statement two

In language definition, `behavior undefined' means `anything can
happen', including a runtime error that brings down the program.
There are lots of examples in the C standard.

Norman

------------------------------------------------------------------------

From: [e-mail] (Nevin Liber)
Date: 29 Nov 1993 07:45:59 -0700
Organization: University of Arizona CS Department, Tucson AZ

In article <[e-mail]>,
Norman Ramsey <[e-mail]> wrote:
>In article <2daf8u$[e-mail]>,
>Nevin Liber <[e-mail]> wrote:
>>>  - inserted elements might be generated, might not
>>>  - the behavior of the construct is undefined

>In language definition, `behavior undefined' means `anything can
>happen', including a runtime error that brings down the program.
>There are lots of examples in the C standard.

But I don't find the statement "Anything can happen except a runtime
error, theomonuclear war, etc." any more useful than saying "Anything
can happen" (undefined).

If you believe otherwise, please post a code fragment where you can do
something useful with "inserted elements might or might not be
generated" as the semantics vs "undefined" as the semantics.

Sentences with the phrases "might", "might not", "may", "may not",
"might or might not", "may or may not" are pretty much unnecessary in a
technical definition.  They are useful only for pointing something out the
reader might have overlooked.  You can exchange any one of the above
phrases with any other one of the above phrases or take the whole
sentence out without changing the meaning of the definition.
--
    Nevin ":-)" Liber    [e-mail]    [phone]

------------------------------------------------------------------------

From: [e-mail] (Norman Ramsey)
Organization: Bellcore, Morristown NJ
Date: Mon, 29 Nov 1993 23:04:11 GMT

>But I don't find the statement "Anything can happen except a runtime
>error, theomonuclear war, etc." any more useful than saying "Anything
>can happen" (undefined).
>
>If you believe otherwise, please post a code fragment where you can do
>something useful with "inserted elements might or might not be
>generated" as the semantics vs "undefined" as the semantics.

Under the invariant that no value in t has type integer,

  every type(x := !s) == "integer" do insert(s, t[x])

is safe and well defined in the maybe, maybe not semantics.  In the
undefined semantics it's unsafe and I'm forced to write

  ss := set()
  every type(x := !s) == "integer" do insert(ss, t[x])
  every insert(s, !ss)